package cn.zifangsky.stack.questions;

import cn.zifangsky.stack.LinkStack;
import cn.zifangsky.stack.Stack;

/**
 * 改进栈，getMinimum() 操作的时间复杂度为O(1)
 * @author zifangsky
 *
 */
public class AdvancedStack implements Stack<Integer>{
	private Stack<Integer> elementStack = new LinkStack<>();
	private Stack<Integer> minStack = new LinkStack<>();
	
	
	@Override
	public boolean isEmpty() {
		return elementStack.isEmpty();
	}

	@Override
	public boolean isFull() {
		return false;
	}

	/**
	 * minStack入栈：当入栈元素小于等于当前minStack栈的最小值时才入栈
	 */
	@Override
	public void push(Integer data) {
		elementStack.push(data);
		
		if(minStack.isEmpty() || data <= minStack.top()){
			minStack.push(data);
		}
	}

	/**
	 * minStack出栈：当elementStack出栈元素等于当前minStack栈的值时才出栈
	 */
	@Override
	public Integer pop() {
		Integer result = elementStack.pop();
		
		if(result == minStack.top()){
			minStack.pop();
		}
		return result;
	}
	
	/**
	 * 获取当前栈的最小值
	 * @时间复杂度 O(1)
	 * 
	 * @return
	 */
	public Integer getMinimum(){
		if(!minStack.isEmpty()){
			return minStack.top();
		}else{
			return null;
		}
	}

	@Override
	public Integer top() {
		return elementStack.top();
	}

	@Override
	public int size() {
		return elementStack.size();
	}

	@Override
	public void deleteStack() {
		elementStack.deleteStack();
		minStack.deleteStack();
	}

	@Override
	public void print() {
		elementStack.print();
	}

}
